package com.xiayuanxing.arithmetic.DataStructures.Search;

/**
 * @program: arithmetic
 * @description: 插值查找算法
 * @author: xia yuan xing
 * @create: 2021-09-29 10:47
 */
public class InsertValueSearch {

    public static void main(String[] args) {

        int[] array = new int[100];
        for (int i = 0; i <100 ; i++) {
            array[i] = i +1;
        }

        int i = insertValueSearch(array, 0, array.length-1, 88);
        System.out.println("下标为："+i);
    }


    /**
     * 插值查找算法
     * @param array 原始数组
     * @param left 左边索引
     * @param right 右边索引
     * @param findValue 要查找的值
     * @return 被查找到的值的下标索引
     */
    public static int insertValueSearch(int[] array,int left,int right,int findValue){

        System.out.println("hello!");
        //findValue < array[0] || findValue > array[array.length -1] 防止mid越界
        if (left > right || findValue < array[0] || findValue > array[array.length -1]){
            return  -1;
        }

        //求出mid
        int mid = left + (right - left) * (findValue - array[left]) / (array[right] - array[left]);

        int midValue = array[mid];

        if (findValue > midValue){
            //向右递归
            return insertValueSearch(array,mid + 1,right,findValue);
        }else if (findValue < midValue){
            //向左递归
            return insertValueSearch(array,left,mid - 1,findValue);
        }else {
            return mid;
        }



    }

}